/**
 * 给定二维数组，再给定一个数K(<50)，问从起点到终点且被K整除的路径总数
 * 令 D[i][j][k] 为从起点到(i,j)且余数为k的路径数量
 * D[N-1][M-1][0]是答案
 */
using llt = long long;
llt const MOD = 1E9 + 7;
llt const None = -1;


class Solution {

using vll = vector<llt>;
using vvll = vector<vll>;

int N, M, K;
vector<vvll> D;

public:
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        N = grid.size();
        M = grid[0].size();
        K = k;
        D.assign(N, vvll(M, vll(K, None)));

        D[0][0][grid[0][0] % K] = 1;
        for(int i=0;i<N;++i)for(int j=0;j<M;++j){
            if(0 == i and 0 == j) continue;

            auto v = grid[i][j];
            if(i > 0){
                for(int k=0;k<K;++k){
                    chkaddAss(D[i][j][(k + v) % K], D[i - 1][j][k]);
                }
            }
            if(j > 0){
                for(int k=0;k<K;++k){
                    chkaddAss(D[i][j][(k + v) % K], D[i][j - 1][k]);
                }                
            }
        }

        return D[N - 1][M - 1][0] == None ? 0 : D[N - 1][M - 1][0];
    }

    void chkaddAss(llt & d, llt a){
        if(None == a) return;
        if(None == d) return (void)(d = a);
        d = (d + a) % MOD;
    }
};